In the applicant's UK Patent No. 2281682, there is described a 3-D rendering system for polygons in which each object is seen to be viewed as defined in a set of surfaces which are infinite. Each elementary area of the screen (e.g. pixel) in which an image is to be displayed has a ray projected through it from a viewpoint into the 3-D scene. The location of the intersection of the projected ray with each surface is then determined. From these intersections, it is then possible to determine whether any intersected surface is visible at that elementary area. The elementary area is then shaded for display in dependence on the results of the determination.
The system can be implemented in a pipeline type processor comprising a number of cells, each of which can perform an intersection calculation with a surface. Thus, a large number of surface intersections can be computed simultaneously. Each cell is loaded with a set of coefficients defining the surface for which it is to perform the intersection test.
An improvement to this arrangement is described in the applicant's UK Patent No. 2298111. In that document, the image is divided into sub-regions or tiles and the tiles can be processed in turn. It is proposed to use a variable tile size and to project a bounding box around complete objects so that only those tiles falling within the bounding box require processing. This is done by determining the distribution of objects on the visible screen, in order for a suitable tile size to be selected. The surfaces which define the various objects are then stored in a list, known as the display list, thereby avoiding the need to store identical surfaces for each tile, since one object made of many surfaces could appear in a number of tiles. Object pointers which identify the objects in the display list are also stored. There is one object pointer list per tile. The tiles can then be rendered in turn using the ray casting technique described above until all objects within each tile are processed. This is a useful method because no effort needs to be made to render objects which are known not to be visible in a particular tile.
A further improvement on this system is proposed in the applicant's International Patent Application No. PCT/GB99/03707, in which any tiles within the bounding box which are not required to display a particular object are discarded before rendering.
FIG. 1 shows the type of processor 101 used in the existing systems described above. Essentially, there are three components. The tile accelerator unit (TA) 103 performs the tiling operation i.e. selects a suitable tile size and divides the visible screen into tiles, and supplies the tile information i.e. the 3-D object data for each tile, to the display list memory 105. The image synthesis processor (ISP) 107 uses the 3-D object data in the display list memory to perform the ray/surface intersection tests discussed above. This produces depth data for each elementary area of the visible screen. After this, the derived image data from the ISP 107 is supplied to texturing and shading processor (TSP) 109 which applies texturing and shading data to surfaces which have been determined as visible and outputs image and shading data to a frame buffer memory 111. Thus, the appearance of each elementary area of the display is determined so as to represent the 3-D image.
In the systems described above, a problem may arise as the complexity of the scene to be rendered increases. Complex scenes require more 3-D object data for each tile to be stored in the display list memory and this means that storage requirements increase. If the display list memory runs out of space, parts of the scene may simply not be rendered and this type of image corruption is becoming less and less acceptable.
In order to solve this problem, the applicant's International Patent Application No. PCT/GB01/02536 proposes the idea of partial rendering. The state of the system (ISP and TSP) is stored to memory before rendering of a tile is complete, and the state is reloaded at a later time in order to finish the rendering. This process is referred to as “z/frame buffer load and store”.
The screen is divided up into a number of regions called macro-tiles, each macro-tile consisting of a rectangular region of the screen. Memory in the display list is then divided into blocks and these are listed in a free store list. Blocks from the free store are then allocated to the macro-tiles as required. The tiling operation stores data associated with each macro-tile in each block. (The tiling operation performed by the TA fills the display list memory so is sometimes referred to as Memory Allocation.) When the display list memory fills up, or reaches some predefined threshold, the system selects a macro-tile, performs a z/frame buffer load, and renders the contents of the macro-tile before saving it using a z/frame buffer store operation. Thus, depth data for the macro-tile is stored according to the data loaded into the display list so far. Upon completion of such a render, the system frees any memory blocks associated with that macro-tile, thereby making them available for further storage. (Because the rendering process frees up display list memory space, it is known as Memory De-Allocation.) So, the scene for each tile is constructed by a number of tiling operations followed by partial renders. Each partial render updates the depth data stored. This means that an upper bound on the memory consumption is imposed and also the memory bandwidth consumed by the system is minimised.
One example of a type of processor used in the partial rendering system is shown in FIG. 2. It can be seen that this is a modified version of FIG. 1. A z buffer memory 209 is linked to the ISP 207 via a z compression/decompression unit 211. This comes into operation when the system is rendering a complex scene and the display list memory 205 is not large enough to contain all the surfaces which need to be processed for a particular tile. The display list will be loaded with data by the TA 203 for all the tiles until it is substantially full (or until a predefined threshold is reached.) This may, however, only represent a portion of the initial data. The image is rendered one tile at a time by ISP 207. The output data for each tile is provided to TSP 213, which uses texture data to texture the tile. At the same time, because the image data was incomplete, the result (i.e. depth data) from ISP 207 is stored to buffer memory 209 via compression/decompression unit 211 for temporary storage. The rendering of the remaining tiles then continues with the incomplete image data until all the tiles have been rendered and stored in frame buffer memory 215 and in z buffer memory 209.
The first part of the display list is then discarded and the additional image data read into it. As processing is performed for each tile in turn by ISP 207, the relevant portion of data from z buffer memory 209 is loaded via the z compression/decompression unit 18 so that it can be combined with the new image data from display list memory 205. The new depth data for each tile is then fed to TSP 213 which combines it with texture data before supplying it to the frame buffer 215.
This process continues for all the tiles in the scene and until all the image data has been rendered. Thus, it can be seen that the z buffer memory fills a temporary store which enables a smaller display list memory to be used than would be necessary for rendering particularly complex scenes. The compression/decompression unit 211 is optional but it enables a smaller z buffer memory to be used.
So, as discussed in International Patent Application No. PCT/GB01/02536, once the display list memory fills up, or reaches a certain threshold, the system selects a macro-tile to render in order to free up some display list memory. In that application, the selection of the macro-tile to render depends on a number of factors, for example the macro-tile which will release the most memory back to the free-store may be chosen.
The inventors of the present invention have seen that various improvements could be made to the memory management in that system.
It is an object of the present invention to provide a memory management system and method which reduces the memory footprint and improves performance when compared with known systems described above. It is a further object of the present invention to provide a memory management system and method which can deal with several applications running simultaneously.